package leetCode.offer49;


/**
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 * 示例:
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 * 说明:
 * 1是丑数,n不超过1690。
 */
public class Solution1 implements Solution{


    @Override
    public int nthUglyNumber(int n) {
        if(n<7) return n;
        int cur = 6;
        for(int i=6;i<n;i++){
            if(isUglyNumber(cur+1)){
                cur = cur+1;
            }else {
                cur = cur+1;
                i--;
            }
        }
        return cur;
    }

    boolean isUglyNumber(int num) {
        if(num%2==0){
            num/=2;
            if(num%3==0||num%5==0||num%2==0) {
                if(num>5)
                  return isUglyNumber(num);
                else return true;
            }
        }

        if(num%3==0){
            num/=3;
            if(num % 5 == 0||num%2==0||num%3==0) {
                if(num>5)
                    return isUglyNumber(num);
                else return true;
            }
        }

        if(num%5==0){
            num/=5;
            if(num % 5 == 0 || num % 2 == 0 || num % 3 == 0){
                if(num>5)
                    return isUglyNumber(num);
                else return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution s = new Solution1();
        long start = System.currentTimeMillis();
        //for(int i=1;i<100;i++){
            System.out.print(s.nthUglyNumber(1690)+" ");
        //}
        System.out.println("耗时："+ (System.currentTimeMillis()-start)+" ms");

    }



}
